# -*- coding: utf-8 -*-
from structures.hashtable import HashTable


class UnionFind():

    def __init__(self, items):
        self.sets = HashTable()
        for item in items:
            node = UnionFindNode(item)
            self.sets.set(item, node)
        self.__count = len(items)

    def find(self, item):
        node = self.sets.get(item)
        while node.set is not None:
            node = node.set
        return node.item

    def union(self, item1, item2):
        if item1 != item2:
            node1 = self.sets.get(item1)
            node2 = self.sets.get(item2)

            if node1.size < node2.size:
                node1.set = node2
                node2.size += node1.size
            else:
                node2.set = node1
                node1.size += node2.size
            self.__count -= 1

    def count(self):
        return self.__count


class UnionFindNode():

    def __init__(self, item):
        self.item = item
        self.set = None
        self.size = 1
